package PrimitiveDataStructures;


import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;


/**
 * 
 * An implementation of a balanced binary search tree key-value associative map data structure.
 * 
 * @author Yevgeny Levanzov & Daniel Samuelov
 *
 */
public class MyBinaryTree<K,V> implements KeyValueDataStructure<K,V> {


	//a class for binary tree key-value entry pair.
	private class Entry implements Comparable<Entry> {
		
		private K key;
		private V value;
		
		/**
		 * A constructor. 
		 * 
		 * @param key the key
		 * @param val the value
		 */
		public Entry(K key, V val) {
			
			this.key = key;
			this.value = val;
		}
		
		/**
		 * Getter for key.
		 * 
		 * @return the key
		 */
		public K getKey() {
			
			return key;
		}
		
		/**
		 * Getter for value.
		 * 
		 * @return the value
		 */
		public V getValue() {
			
			return value;
		}
		
		
		/**
		 * Setter for value.
		 * 
		 * @param val the new value
		 */
		public void setValue(V val) {
			
			this.value = val;
		}
		

		/* (non-Javadoc)
		 * @see java.lang.Comparable#compareTo(java.lang.Object)
		 */
		@SuppressWarnings("unchecked")
		public int compareTo(Entry o) {
			
			List<String> thisKey = (List<String>)(this.getKey());
			List<String> otherKey = (List<String>)(o.getKey());
			
			Collections.sort(thisKey);
			Collections.sort(otherKey);
			
			//comparing by lexicographic order of strings.
			for (int i = 0; i < thisKey.size(); i++) {
				
				if (thisKey.get(i).compareTo(otherKey.get(i)) == 0) {
					continue;
				} else {
					
					return thisKey.get(i).compareTo(otherKey.get(i));
				}
			}
			
			
			if (thisKey.size() > otherKey.size()) {
				return 1;
			} else {
				return -1;
			}
			
		}
		
		/* (non-Javadoc)
		 * @see java.lang.Object#equals(java.lang.Object)
		 */
		@SuppressWarnings("unchecked")
		@Override
		public boolean equals(Object o) {
			
			return this.key.equals(((Entry)o).getKey());
		}
		
		/* (non-Javadoc)
		 * @see java.lang.Object#toString()
		 */
		@Override
		public String toString() {
			
			return "-- " + key + " --> " + value;
		}
		
	}  //end of class Entry.

	
	
	private TreeSet<Entry> ts;

	
	/**
	 * Default constructor.
	 * 
	 */
	public MyBinaryTree() {
		
		this.ts = new TreeSet<Entry>();
	}
	
	
	/* (non-Javadoc)
	 * @see PrimitiveDataStructures.KeyValueDataStructure#size()
	 */
	public int size() {
		
		return this.ts.size();
	}
	

	/* (non-Javadoc)
	 * @see PrimitiveDataStructures.KeyValueDataStructure#isEmpty()
	 */
	public boolean isEmpty() {
		
		return this.ts.isEmpty();
	}
	
	

	/* (non-Javadoc)
	 * @see PrimitiveDataStructures.KeyValueDataStructure#containsKey(java.lang.Object)
	 */
	public boolean containsKey(K key) {
		
		for (Entry e : this.ts) {
			
			if (e.getKey().equals(key)){
				return true;
			}
		}
		
		return false;
	}
	

	/* (non-Javadoc)
	 * @see PrimitiveDataStructures.KeyValueDataStructure#get(java.lang.Object)
	 */
	public V get(K key) {
		
		for (Entry e : this.ts) {
			
			if (e.getKey().equals(key)){
				return e.getValue();
			}
		}
		
		return null;
	}
	

	/* (non-Javadoc)
	 * @see PrimitiveDataStructures.KeyValueDataStructure#put(java.lang.Object, java.lang.Object)
	 */
	public void put(K key, V value) {
		
		for (Entry e : this.ts) {
			
			if (e.getKey().equals(key)){
				
				e.setValue(value);  //update value.
				return;
			}
		}
		
		Entry e = new Entry(key, value);
		this.ts.add(e);

	}

	
	/* (non-Javadoc)
	 * @see PrimitiveDataStructures.KeyValueDataStructure#remove(java.lang.Object)
	 */
	public void remove(K key) {
		
		for (Entry e : this.ts) {
			
			if (e.getKey().equals(key)) {
				this.ts.remove(e);
				return;
			}
		}
		
	}
	
	/* (non-Javadoc)
	 * @see PrimitiveDataStructures.KeyValueDataStructure#keySet()
	 */
	public Set<K> keySet() {
		
		Set<K> ret = new HashSet<K>();
		
		for (Entry e : this.ts) {
			
			ret.add(e.getKey());
		}
		return ret;
	}
	
	/* (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		
		return ts.toString();
	}
	
}
